package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC131 {


    public List<List<String>> partition(String str) {
        List<List<String>> res = new ArrayList<>();
        if (null == str || str.length() <= 0) {
            return res;
        }

        if (str.length() == 1) {
            res.add(new ArrayList<>(Arrays.asList(str)));
            return res;
        }

        Set<List<String>> palindromeSet = new HashSet<>();
        for (int i = 0; i < str.length(); i++) {
            if (!isPalindrome(str, 0, i)) {
                continue;
            }

            List<List<String>> subPartition = partition(str.substring(i + 1));
            for (List<String> subEle : subPartition) {
                List<String> curPart = new ArrayList<>();
                curPart.add(str.substring(0, i + 1));
                curPart.addAll(subEle);
                res.add(curPart);
            }

            if (subPartition.size() == 0) {
                res.add(new ArrayList<>(Arrays.asList(str.substring(0, i + 1))));
            }

        }

        return res;
    }

    boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) return false;
            ++start;
            --end;
        }
        return true;
    }

    public static void main(String[] args) {
        String test = "bb";
        LC131 an = new LC131();
        System.out.println(an.partition(test));
    }
}
